This invention relates to the field of network analysis, and in particular to a technique for determining node location based on limited traffic trace information.
A variety of tools have been developed, and continue to be developed, to facilitate the management of communication networks, and in particular for managing networks that provide communications among computer devices. Many of these tools are configured to model the network's performance under a variety of traffic conditions, both real and hypothesized, and in many cases, base this performance on data collected from the actual network.
Network monitoring devices, commonly referred to as “sniffers” or “protocol analyzers”, are often used to capture traffic flow information. Such devices are placed at various points within the network and are configured to monitor the traffic flowing through that point. Generally, these traffic monitoring devices create a record of each message's header information and the time at which the message was detected; if the monitoring device is configured to monitor multiple communication paths at its location, the path information is also stored in the record. The collection of records from one or more monitoring devices is termed ‘trace information’. Ideally, a network monitoring device would be placed at each node location in a network, so that the time of occurrence (transmission or reception) of each message is accurately recorded. Often, however, the number of monitoring devices is substantially less than the number of nodes of a network, and the times of occurrence of each message at each node can only be estimated, based on the limited availability of trace information.
This limited trace information is often provided in an environment of limited network configuration information, including the lack of information regarding the location of each node in the network. Often, the network configuration is determined by querying devices at each node for their connectivity information, but such connectivity information generally provides only a logical structure of the network, and not its physical structure. That is, it may be apparent that node A is connected to nodes B, C, and D, and node B is connected to node D but not node C, and so on, but the locations, both relative and absolute, of each of the nodes may be unknown.
The location of each node of a network is often a significant parameter in the modeling of a network, particularly when timing characteristics, such as communication delay, is modeled. Such modeling is often hierarchical in nature, such that different models are used dependent upon whether the nodes are local to, or distant from, each other. If, for example, clusters of nodes, such as nodes in a local area network (LAN), are identified, different models may be used to model within-cluster and between-cluster communications. The between-cluster communication models may include, for example, an estimate of the actual distance between clusters, so that the physical propagation delay (distance divided by speed) may be included in the model. In other models, the mere fact that the nodes are substantially distant from each other is of significance, to determine whether to include delays associated with gaining access to a long-distance or wide area network (WAN).
FIGS. 1A-1C illustrate a sequence of messages 1-24 communicated between two nodes, A and B, and three possible configurations of monitoring devices X, Y, Z. In FIG. 1A, the monitoring device X is local to node A and remote from node B; in FIG. 1B, the monitoring device Y is remote from both nodes A and B; and in FIG. 1C, the monitoring device Z is remote from node A, and local to node B. The example of FIG. 1B is provided for completeness; generally, monitoring devices are co-located with a node, either directly connected to the node, or positioned on a LAN that is directly coupled to the node.
As illustrated by the time-lines associated with the monitors X, Y, and Z, the messages 1-24 will be reported as occurring at different times, dependent upon the location of each of the monitors X, Y, and Z. FIGS. 2A-2C illustrate the corresponding trace information (time of occurrence, source node, and destination node) that would be recorded by each of these monitors. Other information, such as the size of the message and related protocol information will also generally appear in the recorded trace information.
Although the trace information in FIGS. 2A-2C is informative, most analysis tools require the information content of FIGS. 1A-1C; in particular, an analysis tool that addresses communications between nodes A and B would generally require information regarding the actual sequence of the messages 1-24 between the nodes. As can be seen, however, because of the different times of appearance of each message 1-24 at each of the monitors, the actual sequence of the messages 1-24 is not immediately apparent from the trace information of FIGS. 2A-2C. The example of FIG. 2B illustrates the actual time-sequence of the messages 1-24, but without knowing that monitoring device Y is located midway between the nodes A-B, the trace information does not provide a basis for determining that the sequence of FIG. 2B is any more or less reflective of actual time-sequence than the sequences of FIGS. 2A or 2C. That is, without knowing the relative location of the monitoring device used to create the given trace information 2A, 2B, or 2C, it is virtually impossible to create the message-sequence diagram of FIGS. 1A-1C from the given trace information.
Conventionally, the physical location of each monitoring device is known to the network manager, because the network manager will generally have placed the monitoring devices at select locations throughout the network. The physical location of each node on the network, on the other hand, must generally be provided by the users of the network, and obtaining this information from each user can be a time-consuming and often infeasible task.
It is an objective of this invention to facilitate a determination of the location of nodes in a network. It is a further objective of this invention to provide this location determination with minimal a priori information from the users of the network. It is a further objective of this information to reduce the number of users of a network that must be contacted to determine the location of each node in a network.
These objectives, and others, are achieved by a method and system that determines the location of nodes in a network relative to the location of monitoring devices that collect trace information on the network. By appropriate sorting, filtering, and characterizing the trace information, nodes are identified as being local to or remote from each monitoring device that detects traffic to or from the node. If the trace information is insufficient to determine the relative location of a node, the node is identified as such. By identifying the nodes whose locations can be determined automatically by this analysis of the trace information, the number of nodes whose locations must be determined by more costly manual methods can be substantially reduced.
Throughout the drawings, the same reference numerals indicate similar or corresponding features or functions. The drawings are included for illustrative purposes and are not intended to limit the scope of the invention.